package main.回溯;

/**
 * @author tmh
 * @date 2024/7/21 22:33
 * @description
 */
public class T79单词搜索 {
    private static final int[][] DIRECTIONS = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
    private int len;
    private int col;
    private int row;
    private boolean[][] visited;
    private char[] charArray;
    private char[][] board;

    public boolean exist(char[][] board, String word) {
        row = board.length;
        if (row == 0) {
            return false;
        }
        col = board[0].length;
        len = word.length();
        charArray = word.toCharArray();
        visited = new boolean[row][col];
        this.board = board;
        //遍历图
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                //判断，如果递归得到的结果是true的话，那么就返回true
                if (dfs(i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }

    //begin代表的是字符串中每个字符的下标
    private boolean dfs(int x, int y, int begin) {
        if (begin == len - 1) {
            return board[x][y] == charArray[begin];
        }
        //如果当前字符根字符串中的字符相同，就进行接下来的逻辑
        if (board[x][y] == charArray[begin]) {
            //把当前位置标记为访问过
            visited[x][y] = true;
            for (int[] direction : DIRECTIONS) {
                int newX = x + direction[0];
                int newY = y + direction[1];
                //如果移动之后的下标在范围里面同时没有被访问过的话，就继续下面的逻辑
                if (inArea(newX, newY) && !visited[newX][newY]) {
                    //如果往下递归后得到的结果是true,那么就返回true
                    if (dfs(newX, newY, begin + 1)) {
                        return true;
                    }
                }
            }
            visited[x][y] = false;
        }
        return false;
    }

    private boolean inArea(int x, int y) {
        return x >= 0 && x < row && y >= 0 && y < col;
    }
}
